package leetcode.February;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Leetcode42【接雨水】
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class CollectRain {
    //定义两个数组分别取左右两个方向的元素一段最大值取交集
    public int trap(int[] height) {
        int value = 0;
        int heightLength = height.length;
        if (heightLength < 3){
            return 0;
        }

        int[] leftMaxArray = new int[heightLength];
        int[] rightMaxArray = new int[heightLength];
        leftMaxArray[0] = height[0];//端元素存不住水但是有可能是后续元素的最大值所以要手动赋值进行初始化
        rightMaxArray[heightLength - 1] = height[heightLength - 1];

        for (int i = 1; i < heightLength; i++) {
            leftMaxArray[i] = Math.max(leftMaxArray[i - 1] , height[i]);
        }
        for (int i = heightLength - 2; i >= 0 ; i--) {
            rightMaxArray[i] = Math.max(rightMaxArray[i + 1] , height[i]);
        }
        for (int i = 0; i < heightLength; i++) {
            //去掉每个元素的底，就是刚好满足之间距离中不同元素的高度不同,取交集后是不考虑当前高度的最大存量，减去当前高度就是实际存量
            value += Math.min(leftMaxArray[i] , rightMaxArray[i]) - height[i];//- height[i]这一步就是这道题的灵魂
        }
        return value;
    }
}
